The present invention relates to computer aided design.
Conventional computer aided design (“CAD”) systems allow a user to design structures and devices that include a number of components. Typically, CAD system components can include one or more stored object models representing standard structures such as windows, doors, or other mechanical or design objects. In some CAD systems, the object models can include one or more numerical fields through which an object can be modified.
Typically, an object can include a number of editable elements that define the object. For example, FIG. 1A illustrates a window object 100. The window object includes three elements, which define the window object 100. A width element 102, a height element 104, and a model number element 106. The model number may define the geometry of window 100 as well as the dimensions. Similarly, specific values for height 104 and width 102 elements can define a particular model number 106 for the window 100.
Elements of an object can depend on other elements of the object and the objects can depend on other objects. Object dependencies can exist between heterogeneous elements and homogeneous elements. Heterogeneous elements typically include elements representing text, geometry, and dimensions. Homogenous elements typically include numerical fields. Conventional fields can have dependencies, where values are calculated from the resultant values from other fields. Fields can be embedded as properties of elements or, alternatively, as sub elements of complex elements such as tables. Typically fields can also be edited, for example, by user input.
Conventionally, dependency relationships between elements of an object or between different objects can be described by dependency graphs. FIG. 1B shows a dependency graph 120 for the window object 100 of FIG. 1A. The dependency graph 120 shows a representation of the relationships between elements in window object 100 where each element of the window object 100 is represented by interconnected nodes. The window dimension node 122 can be manipulated by editing the values in the other nodes because the window dimension has been defined as depending upon the height 104 and the width 102 of the window object 100. The width node 124, height node 126, and model number node 128 can be edited. A pair of oppositely directed arrows 130 indicates that the dependencies are simultaneously considered, resulting in a cyclic directed dependency graph. When objects include cyclic dependencies, determining the order in which dependent nodes are evaluated can be complex.
In other cases, the dependencies are not cyclic. FIG. 2 shows an example of an acyclic dependency graph 200 relating area to width and height. The dependency is formula driven in that the width is defined as a function of height (e.g., Width=2×Height) and the area is defined as a function of both the width and the height (Area=Width×Height). As a result, an edit to height node 202 results in a change in the width node 204. Additionally, the area node 206 then depends on the value of the height node 202 and the width node 204. The dependencies are shown by directed arrows 208 called edges.
When the object dependencies form a directed acyclic graph, the evaluation of the dependencies based on an edit to an node can be determined using, for example, a topological sort of the directed acyclic graph. In one implementation, a topological sorting technique can be used to evaluate the order of a directed acyclic graph, such as the directed acyclic graph 200 shown in FIG. 2.
For example, in evaluating the directed acyclic graph 200, a first step can be the removal of any nodes that do not have incoming edges. In the directed acyclic graph 200, the height node 202 does not have any incoming edges. The height node 202 can therefore be removed first. Nodes can be numbered, for example, in ascending order, as they are removed such that height 202 becomes node number one. With the height node 202 removed (along with the associated outgoing edges), the graph is re-evaluated to identify the nodes then having no incoming edges. The nodes without incoming edges after re-evaluation can be removed. In the example, the width node 204 is removed and numbered as node two because once the height node 202 is removed along with the associated outgoing edges, there are no incoming edges to width node 204.
The process can continue in a similar fashion until all the nodes are removed. The area node 206 is therefore the last node removed and numbered as node three. The numbering of the nodes provides an evaluation order such that when the nodes are evaluated in increasing numerical order all the incoming edges to a node being evaluated are from nodes, which have already been evaluated. Additionally, other evaluation techniques can be used to determine the ordering of acyclic dependency systems.